package pl.elka.simulator.core.experiment;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import pl.elka.simulator.core.EnviromentConfiguration;
import pl.elka.simulator.core.Node;
import pl.elka.simulator.core.Position;

public class ConsistencyRaitingCounter {

	public static final float NEIGHBOUR_DISTANCE = 0.7f;//7 metrow
	public static final float NEIGHBOUR_DISTANCE_SQRT = NEIGHBOUR_DISTANCE*NEIGHBOUR_DISTANCE;
	
	public float countConsistency(EnviromentConfiguration cfg,List<? extends Node> nodes, long epochs) {
		
		Position positions[] = new Position[nodes.size()];
		float sumConsistency = 0;
		
		for(int i=0;i<epochs;++i){
			fillPositionsForEpoch(positions,nodes,i);
			float part = consistencyInEpoch(positions,cfg);	
			sumConsistency+= part;
		}
		
		return sumConsistency/epochs;
	}

	private float consistencyInEpoch(Position[] positions,EnviromentConfiguration cfg) {	
		if(positions.length<=1)
			return 1;				
		
		ConsistencyGraph graph = new ConsistencyGraph(positions.length);		
		int id=0;
		for(Position p:positions){
			graph.nodes[id] = new ConsistencyGraphNode(p, id++);
		}
		
		for(int i=0;i<graph.nodes.length;++i){
			ConsistencyGraphNode n = graph.nodes[i];
			for(int j=i+1;j<graph.nodes.length;++j){
				if(n.position.distSqrt(graph.nodes[j].position)<=NEIGHBOUR_DISTANCE_SQRT){
					n.neighbours.add(graph.nodes[j]);
					graph.nodes[j].neighbours.add(n);
				}
			}
		}
		
		int consPartAmount = countConsistencyParts(graph);
		
		return ((float)(positions.length-consPartAmount))/(positions.length-1);
	}

	private int countConsistencyParts(ConsistencyGraph graph) {
		
		int numberOfTrees = 0;
		
		ConsistencyGraphNode visitedStack[] = new ConsistencyGraphNode[graph.nodes.length];
		int stackHead = 0;
		
		Set<ConsistencyGraphNode> visitedNodes = new HashSet<ConsistencyGraphNode>();
		ConsistencyGraphNode cNode = null;
		
		cNode = getFirstNotVisited(graph.nodes,visitedNodes);
		
		while(cNode!=null){
			visitedStack[stackHead] = cNode;
			++stackHead;
			visitedNodes.add(cNode);
						
			cNode = getFirstNotVisited(cNode.neighbours,visitedNodes);
			while(cNode!=null){				
				visitedStack[stackHead++] = cNode;
				visitedNodes.add(cNode);
				cNode = getFirstNotVisited(cNode.neighbours,visitedNodes);
				while(cNode == null && stackHead>0){
					cNode = visitedStack[--stackHead];
					cNode = getFirstNotVisited(cNode.neighbours,visitedNodes);
				}
			}
			++numberOfTrees;
			cNode = getFirstNotVisited(graph.nodes,visitedNodes);
		}		
		
		
		return numberOfTrees;
	}
	
	private ConsistencyGraphNode getFirstNotVisited(Set<ConsistencyGraphNode> neighbours,Set<ConsistencyGraphNode> visitedNodes) {
		for(ConsistencyGraphNode n:neighbours){
			if(!visitedNodes.contains(n))
				return n;
		}
		return null;
	}

	private ConsistencyGraphNode getFirstNotVisited(ConsistencyGraphNode[] nodes, Set<ConsistencyGraphNode> visitedNodes) {
		for(ConsistencyGraphNode n:nodes){
			if(!visitedNodes.contains(n))
				return n;
		}
		return null;
	}

	private void fillPositionsForEpoch(Position[] positions,List<? extends Node> nodes, int epoch) {
		for(int i=0;i<positions.length;++i){
			positions[i] = nodes.get(i).getPath().getPath().get(epoch);
		}
	}

}
